//==========================================================================
// Copyright (c) 2000-2008,  Elastos, Inc.  All Rights Reserved.
//==========================================================================
#define __NO_LINKNODE_CONSTRUCTOR

#include <csdetect.h>
#include <assert.h>
#include <malloc.h>
#include <stdio.h>
#include <linknode.h>

#ifdef CRITICAL_SECTION_DEADLOCK_DETECT

SpinLock g_csSpinlock;

typedef struct WaitThreadIDNode : public DLinkNode {
    int nID;
} WaitThreadIDNode;

typedef struct CSDetectionNode : public DLinkNode {
    CriticalSection *pCS;
    DLinkNode waitListHead;
} CSDetectionNode;

const int c_csSize = 1024;

CSDetectionNode g_csDetect[c_csSize];
DLinkNode g_usedCSDetectList;
DLinkNode g_freeCSDetectList;

WaitThreadIDNode g_csWait[c_csSize];
DLinkNode g_freeCSWaitList;

CriticalSection *g_cs[c_csSize];
int g_threadID[c_csSize];

int g_uCSNum = 0;
int g_uThreadIDNum = 0;

_ELASTOS Boolean IsInCSList(CriticalSection *pCS);

_ELASTOS Boolean IsInCSWaitList(CSDetectionNode *pCSNode, int nID);

CSDetectionNode *GetCSNode(CriticalSection *pCS);

CriticalSection *GetRequestedCS(int nThreadID);

void NumberedCurrentCSAndThreadID();

_ELASTOS Boolean IsInThreadIDPool(int nThreadID);

int GetCSNum(CriticalSection *pCS);

int GetThreadIDNum(int nThreadID);

void OutputDeadLockInfo(int *pArr);

int GetCSNum(CriticalSection *pCS)
{
    for (int i = 0; i < g_uCSNum; i++) {
        if (g_cs[i] == pCS) return i;
    }

    return c_csSize;
}

int GetThreadIDNum(int nThreadID)
{
    for (int i = 0; i < g_uThreadIDNum; i++) {
        if (g_threadID[i] == nThreadID) return i;
    }

    return c_csSize;
}

_ELASTOS Boolean IsInThreadIDPool(int nThreadID)
{
    for (int i = 0; i < g_uThreadIDNum; i++) {
        if (g_threadID[i] == nThreadID) return TRUE;
    }

    return FALSE;
}

void NumberedCurrentCSAndThreadID(int nCurThreadID)
{
    CSDetectionNode *pCSNode;
    g_uCSNum = 0;
    g_uThreadIDNum = 0;

    g_threadID[g_uThreadIDNum++] = nCurThreadID;

    ForEachDLinkNode(CSDetectionNode *, pCSNode, &g_usedCSDetectList)
    {
        g_cs[g_uCSNum++] = pCSNode->pCS;

        if (!IsInThreadIDPool(pCSNode->pCS->nOwnerId)) {
            g_threadID[g_uThreadIDNum++] = pCSNode->pCS->nOwnerId;
        }

        WaitThreadIDNode *pWait;
        ForEachDLinkNode(WaitThreadIDNode *, pWait, &(pCSNode->waitListHead))
        {
            if (!IsInThreadIDPool(pWait->nID)) {
                g_threadID[g_uThreadIDNum++] = pWait->nID;
            }
        }
    }

    assert(g_uCSNum <= c_csSize);
    assert(g_uThreadIDNum <= c_csSize);
}

CriticalSection *GetRequestedCS(int nThreadID)
{
    CSDetectionNode *pCSNode;
    ForEachDLinkNode(CSDetectionNode *, pCSNode, &g_usedCSDetectList)
    {
        WaitThreadIDNode *pWait;
        ForEachDLinkNode(WaitThreadIDNode *, pWait, &(pCSNode->waitListHead))
        {
            if (pWait->nID == nThreadID) {
                return pCSNode->pCS;
            }
        }
    }

    return NULL;
}

EXTERN void CSDeadLockDetection(CriticalSection *pCurCS, int nCurThreadID)
{
    InsertIntoCSList(pCurCS);

    assert(!g_usedCSDetectList.IsEmpty());

    NumberedCurrentCSAndThreadID(nCurThreadID);

    int *pCritialSection = \
                (int *)_alloca((g_uThreadIDNum + g_uCSNum + 1) * sizeof(int));
    assert(pCritialSection != NULL);

    pCritialSection[1] = 0;
    pCritialSection[2] = GetCSNum(pCurCS);

    UInt32 uIndex = 3;

    CriticalSection *pcs = pCurCS;
    int nThreadID = pCurCS->nOwnerId;
    if (nThreadID == g_threadID[0]) return;

    if (0 == pCurCS->nOwnerId) return;

    do {
        pCritialSection[uIndex++] = GetThreadIDNum(nThreadID);
        if (nThreadID == g_threadID[0]) {
            pCritialSection[0] = uIndex;
            printf("\n****************** DEAD LOCK ******************\n");
            OutputDeadLockInfo(pCritialSection);
            printf("\n***********************************************\n");
            return;
        }

        pcs = GetRequestedCS(nThreadID);
        if (NULL == pcs) return;
        pCritialSection[uIndex++] = GetCSNum(pcs);

        assert(nThreadID != pcs->nOwnerId);

        nThreadID = pcs->nOwnerId;
        if (0 == nThreadID) return;
    } while (TRUE);
}

_ELASTOS Boolean IsInCSList(CriticalSection *pCS)
{
    if (GetCSNode(pCS)) return TRUE;

    return FALSE;
}

CSDetectionNode *GetCSNode(CriticalSection *pCS)
{
    assert(pCS != NULL);

    if (g_usedCSDetectList.IsEmpty()) return NULL;

    CSDetectionNode *pCSNode;
    ForEachDLinkNode(CSDetectionNode *, pCSNode, &g_usedCSDetectList)
    {
        if (pCSNode->pCS == pCS) return pCSNode;
    }

    return NULL;
}

EXTERN void InsertIntoCSList(CriticalSection *pCS)
{
    if (IsInCSList(pCS)) return;

    assert(!g_freeCSDetectList.IsEmpty());

    CSDetectionNode *pCSNode = (CSDetectionNode *)g_freeCSDetectList.First();
    pCSNode->Detach();

    pCSNode->pCS = pCS;
    pCSNode->waitListHead.Initialize();
    g_usedCSDetectList.InsertLast(pCSNode);
}

_ELASTOS Boolean IsInCSWaitList(CSDetectionNode *pCSNode, int nID)
{
    WaitThreadIDNode *pWait;
    ForEachDLinkNode(WaitThreadIDNode *, pWait, &(pCSNode->waitListHead))
    {
        if (pWait->nID == nID) {
            return TRUE;
        }
    }

    return FALSE;
}

void OutputDeadLockInfo(int *pArr)
{
    printf("\n");

    for (int i = 1; i < pArr[0] - 1; i++) {
        if ((i != 1) && (i % 2 == 0)) {
            printf(" ---> CriticalSection:%x ====> ", g_cs[pArr[i]]);
        }
        else {
            printf("Thread(ID):%x", g_threadID[pArr[i]]);
        }
    }

    printf("Thread(ID):%x\n", g_threadID[pArr[1]]);
}

EXTERN void InsertIntoCSWaitList(CriticalSection *pCS, int nThreadID)
{
    CSDetectionNode *pCSNode = GetCSNode(pCS);

    assert(pCSNode != NULL);

    assert(!g_freeCSWaitList.IsEmpty());

    assert(!IsInCSWaitList(pCSNode, nThreadID));

    WaitThreadIDNode *pWaitNode = (WaitThreadIDNode *)g_freeCSWaitList.First();
    pWaitNode->Detach();
    pCSNode->waitListHead.InsertLast(pWaitNode);

    pWaitNode->nID = nThreadID;
}

EXTERN void DetachFromCSList(CriticalSection *pCS)
{
    CSDetectionNode *pCSNode = GetCSNode(pCS);

    if (pCSNode == NULL) return;

    pCSNode->Detach();
    g_freeCSDetectList.InsertLast(pCSNode);

    WaitThreadIDNode *pWait;
    pWait = (WaitThreadIDNode *)pCSNode->waitListHead.m_pPrev;
    pWait->m_pNext = g_freeCSWaitList.m_pNext;
    g_freeCSWaitList.m_pNext->m_pPrev = pWait;

    pWait = (WaitThreadIDNode *)pCSNode->waitListHead.m_pNext;
    g_freeCSWaitList.m_pNext = pWait;
    pWait->m_pPrev = &g_freeCSWaitList;
}

EXTERN void DetachFromCSWaitList(CriticalSection *pCS, int nThreadID)
{
    CSDetectionNode *pCSNode = GetCSNode(pCS);

    assert(pCSNode != NULL);

    WaitThreadIDNode *pWait;
    ForEachDLinkNode(WaitThreadIDNode *, pWait, &(pCSNode->waitListHead))
    {
        if (pWait->nID == nThreadID) {
            pWait->Detach();
            g_freeCSWaitList.InsertFirst(pWait);
            return;
        }
    }

    assert(0);
}

EXTERN void InitCSDetection()
{
    g_usedCSDetectList.Initialize();
    g_freeCSDetectList.Initialize();

    g_freeCSWaitList.Initialize();

    for (int i = 0; i < c_csSize; i++) {
        g_freeCSDetectList.InsertLast(&g_csDetect[i]);
        g_freeCSWaitList.InsertLast(&g_csWait[i]);
    }
}

#endif //CRITICAL_SECTION_DEADLOCK_DETECT
